//
// Created by Administrator on 2021/5/14.
//
#include <string>
#include <iostream>
#include <algorithm>
#include <stack>
#include <set>
using namespace std;

class Solution {
public:
    string minRemoveToMakeValid(string s) { // 左右双向遍历各一次
        string ans;
        int left = 0, right = 0; // 计算左右括号数量
        for (auto &x:s) {
            if (x != '(' and x != ')') ans.push_back(x);
            else if (x == '(') {
                ++left;
                ans.push_back(x);
            } else {
                if (left > 0) {
                    ans.push_back(x);
                    --left;
                }
            }
        }
        s = ans;
        ans = "";
        for (auto i = s.rbegin(); i != s.rend(); ++i) {
            if (*i!='(' and *i != ')') ans.push_back(*i);
            else if (*i == ')') {
                ++right;
                ans.push_back(*i);
            }
            else {
                if (right >0) {
                    ans.push_back(*i);
                    --right;
                }
            }
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};
class Solution2 {  // 优秀解答
public:
    string minRemoveToMakeValid(string s) { // 栈匹配 记录要删除的括号
        stack<int> stk;
        set<int> toDeleteIndex;  //使用set记录要删除的的括号下标，方便后续查询某一下标是否需删除
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') stk.push(i);
            else if (s[i] == ')') {
                if (stk.empty()) toDeleteIndex.insert(i); //无左括号与其匹配则将其加到预删除列表
                else stk.pop(); //有左括号与其匹配，则将两者抵消
            }
        }
        while (!stk.empty()) {
            toDeleteIndex.insert(stk.top()); //栈内剩余的下标是未匹配完的左括号下标，均需加到预删除列表中
            stk.pop();
        }
        string ans;
        for (int i = 0; i < s.size(); i++) {
            if (toDeleteIndex.count(i) == 0) ans += s[i]; //如果下标不在预删除列表中，可加到ans中
        }
        return ans;
    }
};


int main() {
    Solution2 sol;
    cout << sol.minRemoveToMakeValid("lee(t(c)o)de)") << endl;
    cout << sol.minRemoveToMakeValid("a)b(c)d") << endl;
    cout << sol.minRemoveToMakeValid("))((") << endl;
    cout << sol.minRemoveToMakeValid("(a(b(c)d)") << endl;
    return 0;
}
